class Solution {//lcr170——交易的逆序对数
private:
    vector<int> tmp;
private:
    int merge_sort(vector<int>&nums,int begin,int end){
        if(begin>=end) return 0;
        int mid=(end-begin)/2+begin;
        //分治
        int a=merge_sort(nums,begin,mid);
        int b=merge_sort(nums,mid+1,end);
        int c=0;
        //归并，并对数组进行排序，并且边排序边算出逆序对的数量
        int cur1=begin,cur2=mid+1,i=begin;
        while(cur1<=mid&&cur2<=end)
        {
            if(nums[cur1]>nums[cur2]){
                tmp[i++]=nums[cur2++];
                c+=mid-cur1+1;
            }
            else tmp[i++]=nums[cur1++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=end) tmp[i++]=nums[cur2++];

        for(int j=begin;j<=end;j++){
            nums[j]=tmp[j];
        }
        return a+b+c;
    }
public:
    int reversePairs(vector<int>& record) {
        int n=record.size();
        tmp.resize(n);
        int ret=merge_sort(record,0,n-1);
        return ret;
    }
};